use std::cmp::max;

/// 一维数组

/// 找到数组的中心位置
/// https://leetcode-cn.com/problems/find-the-middle-index-in-array/
pub fn find_centre_point(nums: Vec<i32>) -> i32 {
    let sum_nums = nums.iter().sum::<i32>();
    let mut prefix_sum = 0i32;
    for i in 0..nums.len() {
        if sum_nums - nums[i] == 2 * prefix_sum {
            return i as i32;
        }
        prefix_sum = prefix_sum + nums[i];
    }
    -1
}

/// 搜索插入位置
/// https://leetcode.cn/leetbook/read/array-and-string/cxqdh/
/// 1. 复杂度为 O(log n) 的算法
pub fn search_insert_index(nums: Vec<i32>, target: i32) -> i32 {
    // 标准的二分查找
    if nums.len() == 0 { return -1; }
    let mut l = 0;
    let mut r = nums.len() - 1;
    while l <= r {
        let mid = (l + r) / 2;
        if nums[mid] == target {
            return mid as i32;
        } else if nums[mid] > target {
            r = mid - 1;
            if mid == 0 { return mid as i32; }
        } else {
            l = mid + 1;
        }
    }

    return l as i32;
}

/// 合并插入区间
/// https://leetcode.cn/leetbook/read/array-and-string/c5tv3/
pub fn merge_both_jointed_array(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    if intervals.len() == 0 { return intervals; }
    intervals.sort_by(|a, b| a[0].cmp(&b[0]));
    let mut result: Vec<Vec<i32>> = Vec::new();
    result.push(intervals[0].clone());
    let mut cur = 0;
    for i in 1..intervals.len() {
        if intervals[i][0] <= result[cur][1] {
            result[cur][1] = max(result[cur][1], intervals[i][1]);
        } else {
            result.push(intervals[i].clone());
            cur = cur + 1;
        }
    }
    result
}


#[test]
fn test_find_centre_point() {
    let vec1 = vec![1, -1, -1];
    let i = find_centre_point(vec1);
    println!("{i}");
}

#[test]
fn test_search_insert_index() {
    let vec1 = vec![1, 3, 5, 6];
    let result = search_insert_index(vec1, 2);
    // let result = vec1.binary_search(&7).unwrap_or_else(|x| x) as i32;

    println!("{result}");
}

#[test]
fn test_merge_both_jointed_array() {
    let mut vec1 = vec![
        vec![1, 3],
        vec![2, 6],
        vec![8, 10],
        vec![15, 18],
    ];
    let vec2 = merge_both_jointed_array(vec1);
    println!("{vec2:?}");
}
